package com.zjj.algorithm.learning.leetcode.matrix;

import java.util.*;

/**
 * 542. 01 矩阵 中档题
 * 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
 * <p>
 * 两个相邻元素间的距离为 1 。
 * <p>
 * 输入：mat = [
 * [0,0,0],
 * [0,1,0]
 * ,[0,0,0]]
 * 输出：
 * [[0,0,0],
 * [0,1,0],
 * [0,0,0]]
 * 输入：mat = [
 * [0,0,0],
 * [0,1,0],
 * [1,1,1]
 * ]
 * 输出：[
 * [0,0,0],
 * [0,1,0],
 * [1,2,1]
 * ]
 * <p>
 * 提示：
 * <p>
 * m == mat.length
 * n == mat[i].length
 * 1 <= m, n <= 104
 * 1 <= m * n <= 104
 * mat[i][j] is either 0 or 1.
 * mat 中至少有一个 0
 *
 * @author zjj_admin
 * @date 2022/11/28 16:53
 */
public class ZeroOneMatrix {

    public static void main(String[] args) {

        int[][] mat1 = {
                {0, 1, 1, 1, 1},
                {1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1}
        };
        int[][] mat2 = {
                {0},
                {0},
                {0}
        };
        updateMatrix(mat1);

    }




    /**
     * 时间
     * 11 ms
     * 击败
     * 76.2%
     * 内存
     * 44.8 MB
     * 击败
     * 36.86%
     * 思路：广度优先
     * 1、循环遍历数组 mat ，当数据为 0 时就加入队列，不为 0 时就修改值为 10000
     * 2、遍历第一次队列中的数据，判断数据的上下左右是不是最小值，若不是最小值就修改成最小值，同时将对应的坐标加入队列
     * 3、重复步骤二，直到队列中没有数据
     *
     * @param mat
     */
    public static void updateMatrix(int[][] mat) {
        int h = mat.length;
        int w = mat[0].length;
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (mat[i][j] == 0) {
                    queue.add(new int[]{i, j});
                }else {
                    mat[i][j] = 10000;
                }
            }
        }
        int min = 0;
        while (!queue.isEmpty()) {
            int x;
            int y;
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                int[] poll = queue.poll();
                x = poll[0];
                y = poll[1];
                if (x - 1 >= 0 && mat[x - 1][y] > min + 1) {
                    mat[x - 1][y] = min + 1;
                    queue.add(new int[]{x - 1, y});
                }
                if (x + 1 < h && mat[x + 1][y] > min + 1) {
                    mat[x + 1][y] = min + 1;
                    queue.add(new int[]{x + 1, y});
                }
                if (y - 1 >= 0 && mat[x][y - 1] > min + 1) {
                    mat[x][y - 1] = min + 1;
                    queue.add(new int[]{x, y - 1});
                }
                if (y + 1 < w && mat[x][y + 1] > min + 1) {
                    mat[x][y + 1] = min + 1;
                    queue.add(new int[]{x, y + 1});
                }
            }
            min++;
        }
    }


}
